/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import java.util.*
import kotlin.math.min

/**
 * Leftist heaps. The heap is sorted according to the [ natural ordering][Comparable] of its keys, or by a [Comparator] provided at heap
 * creation time, depending on which constructor is used.
 *
 *
 *
 * Operations `insert`, `deleteMin`, `decreaseKey`, and
 * `delete` take worst-case O(log(n)). Operation `findMin` is
 * worst-case O(1).
 *
 *
 *
 * Note that the ordering maintained by this heap, like any heap, and whether or
 * not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the `Heap`
 * interface. (See `Comparable` or `Comparator` for a precise
 * definition of *consistent with equals*.) This is so because the
 * `Heap` interface is defined in terms of the `equals` operation,
 * but this heap performs all key comparisons using its `compareTo` (or
 * `compare`) method, so two keys that are deemed equal by this method
 * are, from the standpoint of this heap, equal. The behavior of a heap
 * *is* well-defined even if its ordering is inconsistent with
 * `equals`; it just fails to obey the general contract of the
 * `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */

/**
 * Constructs a new, empty heap, ordered according to the given comparator.
 *
 *
 *
 * All keys inserted into the heap must be *mutually comparable* by
 * the given comparator: `comparator.compare(k1,
 * k2)` must not throw a `ClassCastException` for any keys `k1`
 * and `k2` in the heap. If the user attempts to put a key into the
 * heap that violates this constraint, the `insert(Object key)` call
 * will throw a `ClassCastException`.
 *
 * @param comparator
 * the comparator that will be used to order this heap. If
 * `null`, the [natural ordering][Comparable] of
 * the keys will be used.
 */
/**
 * Constructs a new, empty heap, using the natural ordering of its keys.
 *
 *
 *
 * All keys inserted into the heap must implement the [Comparable]
 * interface. Furthermore, all such keys must be *mutually
 * comparable*: `k1.compareTo(k2)` must not throw a
 * `ClassCastException` for any keys `k1` and `k2` in the
 * heap. If the user attempts to put a key into the heap that violates this
 * constraint (for example, the user attempts to put a string key into a
 * heap whose keys are integers), the `insert(Object key)` call will
 * throw a `ClassCastException`.
 */
class LeftistHeap<K, V>
@JvmOverloads constructor(comparator: Comparator<in K?>? = null) : SkewHeap<K, V>(comparator) {
    // ~-----------------------------------------------------------------------
    inner class LeftistNode(heap: LeftistHeap<K, V>, key: K, value: V?) : Node(heap, key, value) {
        var npl: Int = 0 // null path length
    }

    /**
     * Factory method for new node creation
     *
     * @param key
     * the key
     * @param value
     * the value
     * @return the newly created node
     */
    override fun createNode(key: K, value: V?): LeftistNode{
        return LeftistNode(this, key, value)
    }

    /**
     * Swap the children of a node.
     *
     * @param n
     * the node
     */
    protected fun swapChildren(n: LeftistNode) {
        val left = n.o_c
        if (left != null) {
            val right = left.y_s
            if (right !== n) {
                n.o_c = right
                right!!.y_s = left
                left.y_s = n
            }
        }
    }

    /**
     * Top-down union two skew heaps
     *
     * @param root1
     * the root of the first heap
     * @param root2
     * the root of the right heap
     * @return the new root of the merged heap
     */
    override fun union(root1: Node?, root2: Node?): Node? {
        var root1 = root1
        var root2 = root2
        if (root1 == null) {
            return root2
        } else if (root2 == null) {
            return root1
        }

        val newRoot: Node
        val path: Deque<LeftistNode> = LinkedList()

        // find initial
        var c = (root1.key as Comparable<K?>?)!!.compareTo(root2.key)
        if (c <= 0) {
            newRoot = root1
            root1 = unlinkRightChild(root1)
        } else {
            newRoot = root2
            root2 = unlinkRightChild(root2)
        }
        var cur = newRoot
        path.push(cur as LeftistNode)

        // merge
        while (root1 != null && root2 != null) {
            c = (root1.key as Comparable<K?>?)!!.compareTo(root2.key)
            if (c <= 0) {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root1
                } else {
                    cur.o_c!!.y_s = root1
                }
                root1.y_s = cur
                cur = root1
                path.push(cur as LeftistNode)
                root1 = unlinkRightChild(root1)
            } else {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root2
                } else {
                    cur.o_c!!.y_s = root2
                }
                root2.y_s = cur
                cur = root2
                path.push(cur as LeftistNode)
                root2 = unlinkRightChild(root2)
            }
        }

        if (root1 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root1
            } else {
                cur.o_c!!.y_s = root1
            }
            root1.y_s = cur
        }

        if (root2 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root2
            } else {
                cur.o_c!!.y_s = root2
            }
            root2.y_s = cur
        }

        /*
         * Traverse path upwards, update null path length and swap if needed.
         */
        while (!path.isEmpty()) {
            val n = path.pop()

            if (n.o_c != null) {
                // at least on child
                val nLeft = n.o_c as LeftistNode
                val nplLeft = nLeft.npl
                var nplRight = -1
                if (nLeft.y_s !== n) {
                    // two children
                    val nRight = nLeft.y_s as LeftistNode
                    nplRight = nRight.npl
                }
                n.npl = (1 + min(nplLeft.toDouble(), nplRight.toDouble())).toInt()

                if (nplLeft < nplRight) {
                    // swap
                    swapChildren(n)
                }
            } else {
                // no children
                n.npl = 0
            }
        }

        return newRoot
    }

    /**
     * Top-down union of two leftist heaps with comparator.
     *
     * @param root1
     * the root of the first heap
     * @param root2
     * the root of the right heap
     * @return the new root of the merged heap
     */
    override fun unionWithComparator(root1: Node?, root2: Node?): Node? {
        var root1 = root1
        var root2 = root2
        if (root1 == null) {
            return root2
        } else if (root2 == null) {
            return root1
        }

        val newRoot: Node
        val path: Deque<LeftistNode> = LinkedList()

        // find initial
        var c = comparator!!.compare(root1.key, root2.key)
        if (c <= 0) {
            newRoot = root1
            root1 = unlinkRightChild(root1)
        } else {
            newRoot = root2
            root2 = unlinkRightChild(root2)
        }
        var cur = newRoot
        path.push(cur as LeftistNode)

        // merge
        while (root1 != null && root2 != null) {
            c = comparator.compare(root1.key, root2.key)
            if (c <= 0) {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root1
                } else {
                    cur.o_c!!.y_s = root1
                }
                root1.y_s = cur
                cur = root1
                path.push(cur as LeftistNode)
                root1 = unlinkRightChild(root1)
            } else {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root2
                } else {
                    cur.o_c!!.y_s = root2
                }
                root2.y_s = cur
                cur = root2
                path.push(cur as LeftistNode)
                root2 = unlinkRightChild(root2)
            }
        }

        if (root1 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root1
            } else {
                cur.o_c!!.y_s = root1
            }
            root1.y_s = cur
        }

        if (root2 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root2
            } else {
                cur.o_c!!.y_s = root2
            }
            root2.y_s = cur
        }

        /*
         * Traverse path upwards, update null path length and swap if needed.
         */
        while (!path.isEmpty()) {
            val n = path.pop()

            if (n.o_c != null) {
                // at least on child
                val nLeft = n.o_c as LeftistNode
                val nplLeft = nLeft.npl
                var nplRight = -1
                if (nLeft.y_s !== n) {
                    // two children
                    val nRight = nLeft.y_s as LeftistNode
                    nplRight = nRight.npl
                }
                n.npl = (1 + min(nplLeft.toDouble(), nplRight.toDouble())).toInt()

                if (nplLeft < nplRight) {
                    // swap
                    swapChildren(n)
                }
            } else {
                // no children
                n.npl = 0
            }
        }

        return newRoot
    }

    companion object {
        private const val serialVersionUID = -5948402731186806608L
    }
}
